package com.example.design.leetcode.dfs;

//剑指 Offer 55 - I. 二叉树的深度
//    输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
//
//    例如：
//    给定二叉树 [3,9,20,null,null,15,7]，
//     3
//    / \
//    9  20
//      /  \
//     15   7
//    返回它的最大深度3 。
//
//    提示：
//    节点总数 <= 10000
//    注意：本题与主站 104题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

// 标签：dfs

public class Practice37 {

    public static int maxDepth(TreeNode root) {
        return dfs(root);
    }

    private static int dfs(TreeNode root) {
        // 递归的出口, 如果树直接一个节点都没有，深度为0
        if (root == null) {
            return 0;
        }

        // 获取左子树的深度和右子树的深度，并对比最大值
        int max = Math.max(dfs(root.left), dfs(root.right));

        // 上面一部只是获取了左右子树的深度，还差根节点，把根节点加上
        return max + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode treeNode = new TreeNode(9);
        TreeNode treeNode1 = new TreeNode(20);
        TreeNode treeNode2 = new TreeNode(15);
        TreeNode treeNode3 = new TreeNode(7);
        root.left = treeNode;
        root.right = treeNode1;
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;

        System.out.println(maxDepth(root));
    }
}
